package com.sgj.linkedlist;

import java.util.Stack;

/**
 * 单链表面试题
 * @Author: Guoji Shen
 * @Date: 2021/8/3 13:40
 */
public class Interview {

    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1, "aa", "AAA");
        HeroNode hero2 = new HeroNode(2, "bb", "BBB");
        HeroNode hero3 = new HeroNode(3, "cc", "CCC");
        HeroNode hero4 = new HeroNode(4, "dd", "DDD");

        // 创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByNo(hero3);
        singleLinkedList.addByNo(hero2);
        singleLinkedList.addByNo(hero4);
        singleLinkedList.addByNo(hero1);

        // 题1：获取到单链表有效节点的个数(如果是带头节点的链表，不统计头节点)
        System.out.println("有效的节点个数为[" + getLength(singleLinkedList.getHead()) + "]个");

        // 题2：查找单链表种倒数第k个节点(新浪面试题)
        int index = 2;
        HeroNode res = findLastIndexNode(singleLinkedList.getHead(), index);
        if (res != null) {
            System.out.printf("倒数第[%d]个节点为：%s\n", index, res);
        } else {
            System.out.println("没有找到该节点");
        }

        // 题3：单链表的反转(腾讯面试题)
        System.out.println("====================原链表=====================");
        singleLinkedList.list();
        System.out.println("====================反转单链表=====================");
        reversetList(singleLinkedList.getHead());
        singleLinkedList.list();

        // 题4：从尾到头打印单链表(百度要求  方式1：反向遍历   方式2：Stack栈)
        // 上面的单链表的反转已经实现了这个功能，但是由于这个操作会破坏原来的单链表结构，所以一般不建议方式1
        System.out.println("====================逆序打印单链表=====================");
        reversePrint(singleLinkedList.getHead());

        // 题5：合并两个有序的单链表，合并之后的链表依然有序
    }

    // 题1：获取到单链表有效节点的个数(如果是带头节点的链表，不统计头节点)
    /**
     * @param head 链表的头节点
     * @return 返回有效节点个数
     */
    public static int getLength(HeroNode head) {
        // 判断是否为空链表
        if (head.next == null) {
            return 0;
        }
        int length = 0;
        // 定义一个辅助的变量
        HeroNode cur = head.next;
        while (cur != null) {
            length ++;
            cur = cur.next;
        }
        return length;
    }

    // 题2：查找单链表种倒数第k个节点(新浪面试题)
    /**
     * 编写一个方法，接受head节点，同时接收一个index
     * 先把链表遍历，得到链表总长度  getLength
     * 得到size后，从链表的第一个开始遍历(size-index)个，就可以得到
     * @param head 链表的头节点
     * @param index 表示是倒数第index个节点
     * @return 如果找到了，返回该节点，否则返回null
     */
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        // 判断如果链表为空，返回null
        if (head.next == null) {
            return null;
        }
        // 第一次遍历得到链表的长度(节点个数)
        int size = getLength(head);
        // 第二次遍历 size - index 位置，就是我们倒数的第k个节点
        // 先做一个index的校验
        if (index <= 0 || index > size) {
            return null;
        }
        // 定义一个辅助变量
        HeroNode cur = head.next;
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    // 题3：单链表的反转(腾讯面试题)
    public static void reversetList(HeroNode head) {
        // 如果当前链表为空，或者只有一个节点，无需反转
        if (head.next == null || head.next.next == null) {
            return;
        }
        // 定义一个辅助的指针，帮助我们遍历原来的链表
        HeroNode cur = head.next;
        // 指向当前节点的下一个节点
        HeroNode next = null;
        HeroNode reverseHead = new HeroNode(0, "" ,"");
        // 遍历原来的链表
        // 每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端
        while (cur != null) {
            // 先暂时保存当前节点的下一个节点
            next = cur.next;
            // 将cur的下一个节点指向新的链表的头节点
            cur.next = reverseHead.next;
            // 将cur连接到新的链表上
            reverseHead.next = cur;
            cur = next;
        }
        // 将 head.next 指向 reverseHead.next，实现单链表的反转
        head.next = reverseHead.next;
    }

    // 题4：从尾到头打印单链表(使用方式2)
    public static void reversePrint(HeroNode head) {
        // 判断是否为空链表
        if (head.next == null) {
            return;
        }
        // 创建一个栈，将各个节点压入栈中
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        // 将链表的所有节点压入栈中
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        // 将栈中的节点进行打印，pop 出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }
}